#ifndef __MNM_TILE_GENERATOR_H
#define __MNM_TILE_GENERATOR_H

#pragma once


#include "MNM.h"
#include "Profiler.h"
#include "CompactSpanGrid.h"
#include "Tile.h"
#include "BoundingVolume.h"

#include <SimpleHashLookUp.h>

namespace MNM
{
	class TileGenerator
	{
	public:
		enum
		{
			MaxTileSizeX = 16,
			MaxTileSizeY = 16,
			MaxTileSizeZ = 16,
		};

		struct Params
		{
			Params()
				: origin(ZERO)
				, sizeX(8)
				, sizeY(8)
				, sizeZ(8)
				, voxelSize(0.1f)
				, flags(0)
				, blurAmount(0)
				, minWalkableArea(16)
				, boundary(0)
				, exclusions(0)
				, exclusionCount(0)
				, hashValue(0)
			{
			}

			enum Flags
			{
				NoBorder				= 1 << 0,
				NoErosion				= 1 << 1,
				NoHashTest			= 1 << 2,
				BuildBVTree			= 1 << 3,
				DebugInfo				= 1 << 7,
			};

			Vec3 origin;
			Vec3 voxelSize;

			uint16 flags;
			uint16 minWalkableArea;
			uint16 exclusionCount;

			uint8 blurAmount;
			uint8 sizeX;
			uint8 sizeY;
			uint8 sizeZ;

			struct AgentSettings
			{
				AgentSettings()
					: radius(4)
					, height(18)
					, climbableHeight(4)
					, maxWaterDepth(8)
				{
				}

				uint32 radius : 8;
				uint32 height : 8;
				uint32 climbableHeight : 8;
				uint32 maxWaterDepth : 8;
			} agent;

			const BoundingVolume* boundary;
			const BoundingVolume* exclusions;
			uint32 hashValue;
		};

		enum ProfilerTimers
		{
			Voxelization = 0,
			Filter,
			DistanceTransform,
			Blur,
			ContourExtraction,
			Simplification,
			Triangulation,
			BVTreeConstruction,
		};

		enum ProfilerMemoryUsers
		{
			DynamicSpanGridMemory = 0,
			CompactSpanGridMemory,
			SegmentationMemory,
			RegionMemory,
			PolygonMemory,
			TriangulationMemory,
			VertexMemory,
			TriangleMemory,
			BVTreeConstructionMemory,
			BVTreeMemory,
		};

		enum ProfilerStats
		{
			VoxelizationTriCount = 0,
			RegionCount,
			PolygonCount,
			TriangleCount,
			VertexCount,
			BVTreeNodeCount,
		};

		enum DrawMode
		{
			DrawNone = 0,
			DrawRawVoxels,
			DrawFlaggedVoxels,
			DrawDistanceTransform,
			DrawSegmentation,
			DrawContourVertices,
			DrawNumberedContourVertices,
			DrawSimplifiedContours,
			DrawTriangulation,
			DrawBVTree,
			LastDrawMode,
		};

		bool Generate(const Params& params, Tile& tile, uint32* hashValue);
		void Draw(DrawMode mode) const;

		typedef Profiler<ProfilerMemoryUsers, ProfilerTimers, ProfilerStats> ProfilerType;
		const ProfilerType& GetProfiler() const;
		
		enum SpanFlags
		{
			NotWalkable		= 1 << 0,
			TileBoundary	= 1 << 1,
		};

		enum Labels
		{
			FirstInvalidLabel	= (1 << 12) - 1,
			NoLabel						= FirstInvalidLabel,
			ExternalContour		= 1 << 12,
			InternalContour		= 1 << 13,
			BorderLabelH			= 1 << 14,
			BorderLabelV			= 1 << 15,
		};

	protected:

		typedef std::vector<uint16> SpanExtraInfo;

		struct ContourVertex
		{
			ContourVertex()
			{
			}

			ContourVertex(uint16 _x, uint16 _y, uint16 _z)
				: x(_x)
				, y(_y)
				, z(_z)
				, flags(0)
			{
			}

			uint16 x;
			uint16 y;
			uint16 z;
			uint16 flags;

			enum Flags
			{
				TileBoundary = 1 << 0,
				TileBoundaryV	= 1 << 1,
				Unremovable = 1 << 2,
			};

			bool operator <(const ContourVertex& other) const
			{
				if (x == other.x)
					return y < other.y;
				else
					return x < other.x;
			}

			bool operator ==(const ContourVertex& other) const
			{
				return (x == other.x) && (y == other.y) && (z == other.z);
			}
		};


		typedef std::vector<ContourVertex> Contour;
		typedef std::vector<Contour> Contours;


		struct PolygonVertex
		{
			enum Flags
			{
				Reflex	= 1 << 0,
				Ear			= 1 << 1,
			};

			PolygonVertex(uint16 _x, uint16 _y, uint16 _z)
				: x(_x)
				, y(_y)
				, z(_z)
				, flags(0)
			{
			}

			uint16 x;
			uint16 y;
			uint16 z;
			uint16 flags;

			bool operator <(const ContourVertex& other) const
			{
				if (x == other.x)
					return y < other.y;
				else
					return x < other.x;
			}

			bool operator ==(const ContourVertex& other) const
			{
				return (x == other.x) && (y == other.y) && (z == other.z);
			}
		};

		typedef std::vector<PolygonVertex> PolygonContour;
		typedef std::vector<PolygonContour> PolygonHoles;
		typedef std::vector<PolygonVertex> VoxelContour;

		typedef struct
		{
			PolygonContour contour;
			PolygonHoles holes;
		} Polygon;

		struct Region
		{
			Region()
				: spanCount(0)
				, flags(0)
			{
			}

			enum Flags
			{
				TileBoundary	= 1 << 0,
				TileBoundaryV	= 1 << 1,
			};

			Contour contour;
			Contours holes;

			size_t spanCount;
			size_t flags;

			void swap(Region& other)
			{
				std::swap(spanCount, other.spanCount);

				contour.swap(other.contour);
				holes.swap(other.holes);
			}
		};

		inline size_t BorderSizeH() const
		{
			return (m_params.flags & Params::NoBorder) ? 0 : ((m_params.agent.radius & ~1) + 2);
		}

		inline size_t BorderSizeV() const
		{
			return (m_params.flags & Params::NoBorder) ? 0 : ((m_params.agent.radius & ~1) + 2);
		}

		inline bool IsBorderCell(size_t x, size_t y) const
		{
			const size_t border = BorderSizeH();
			const size_t width = m_spanGrid.GetWidth();
			const size_t height = m_spanGrid.GetHeight();

			return (x < border) || (x >= width - border) || (y < border) || (y >= height - border);
		}

		inline bool IsBoundaryCell(size_t x, size_t y) const
		{
			const size_t border = BorderSizeH();
			const size_t borderV = BorderSizeV();
			const size_t width = m_spanGrid.GetWidth();
			const size_t height = m_spanGrid.GetHeight();

			return (((x == border) || (x == width - border - 1)) && (y >= border) && (y <= height - border - 1))
				|| (((y == border) || (y == height - border - 1)) && (x >= border) && (x <= width - border - 1));
		}

		inline bool IsBoundaryVertex(size_t x, size_t y) const
		{
			const size_t border = BorderSizeH();
			const size_t width = m_spanGrid.GetWidth();
			const size_t height = m_spanGrid.GetHeight();

			return (((x == border) || (x == width - border)) && (y >= border) && (y <= height - border))
				|| (((y == border) || (y == height - border)) && (x >= border) && (x <= width - border));
		}

		inline bool IsCornerVertex(size_t x, size_t y) const
		{
			const size_t border = BorderSizeH();
			const size_t width = m_spanGrid.GetWidth();
			const size_t height = m_spanGrid.GetHeight();

			return (((x == border) || (x == width - border)) && ((y == border) || (y == height - border)));
		}

		inline bool IsBoundaryVertexV(size_t z) const
		{
			const size_t borderV = BorderSizeV();
			
			return (z == borderV) || (z == m_top + borderV);
		}

		size_t VoxelizeVolume(const AABB& volume, uint32 hashValueSeed = 0, uint32* hashValue = 0);
		void FilterWalkable(const AABB& aabb, bool fullyContained = true);
		void ComputeDistanceTransform();
		void BlurDistanceTransform();

		void PaintBorder(uint16* data, size_t borderH, size_t borderV);

		void TraceExternalContour(size_t x, size_t y, size_t top, size_t erosion, size_t climbableVoxelCount, 
			uint16 label, Region& region);
		void TraceInternalContour(size_t x, size_t y, size_t top, size_t erosion, size_t climbableVoxelCount, 
			uint16 label, Region& region);
		void TidyUpContourEnd(Contour& contour);
		size_t ExtractContours();

		void FilterBadRegions(size_t minSpanCount);

		bool SimplifyContour(const Contour& contour, const real_t& tolerance2DSq, const real_t& tolerance3DSq,
			PolygonContour& poly);
		void SimplifyContours();

		typedef simple_hash_lookup<uint32, uint16> VertexIndexLookUp;
		bool MergeHole(PolygonContour& contour, const PolygonContour& hole, const size_t agentHeight,
			const size_t holeVertex) const;
		size_t Triangulate(PolygonContour& contour, const size_t agentHeight, const size_t borderH, const size_t borderV,
			VertexIndexLookUp& lookUp);
		size_t Triangulate();
		void BuildBVTree();

		struct SurroundingSpanInfo
		{
			SurroundingSpanInfo(uint16 _label, size_t _index, size_t _flags = 0)
				: flags(_flags)
				, label(_label)
				, index(_index)
			{
			}
			size_t flags;
			size_t index;
			uint16 label;
		};

		enum NeighbourClassification
		{
			UW = 0, // not walkable
			NB = 1, // walkable, not border
			WB = 2, // walkable, border
		};

		inline NeighbourClassification ClassifyNeighbour(const SurroundingSpanInfo& neighbour, 
			size_t erosion,	size_t borderFlag) const
		{
			if (((neighbour.flags & NotWalkable) != 0) || (m_distances[neighbour.index] < erosion))
				return UW;
			return (neighbour.label & borderFlag) ? WB : NB;
		}

		bool GatherSurroundingInfo(const Vec2i& vertex, const Vec2i& direction, const uint16 top,
			const uint16 climbableVoxelCount, size_t& height, SurroundingSpanInfo& left, SurroundingSpanInfo& front,
			SurroundingSpanInfo& frontLeft) const;
		void DetermineContourVertex(const Vec2i& vertex, const Vec2i& direction, uint16 top,
			uint16 climbableVoxelCount, ContourVertex& contourVertex) const;
		inline bool ContourVertexRemovable(const ContourVertex& contourVertex) const
		{
			return ((contourVertex.flags & ContourVertex::TileBoundary) == 0)
				&& ((contourVertex.flags & ContourVertex::Unremovable) == 0);
		}

		void AddContourVertex(const ContourVertex& vertex, Region& region, Contour& contour) const;

		size_t InsertUniqueVertex(VertexIndexLookUp& lookUp, size_t x, size_t y, size_t z);

		Params m_params;
		ProfilerType m_profiler;
		size_t m_top;

		typedef std::vector<Tile::Triangle> Triangles;
		Triangles m_triangles;

		typedef std::vector<Tile::Vertex> Vertices;
		Vertices m_vertices;

		typedef std::vector<Tile::BVNode> BVTree;
		BVTree m_bvtree;

		CompactSpanGrid m_spanGrid;

		SpanExtraInfo m_distances;
		SpanExtraInfo m_labels;

		typedef std::vector<Region> Regions;
		Regions m_regions;

		typedef std::vector<Polygon> Polygons;
		Polygons m_polygons;

		CompactSpanGrid m_spanGridFlagged;
	};
}

#endif	// #ifndef __MNM_TILE_GENERATOR_H
